package 力扣_树算法.搜索树;

import java.util.ArrayList;
import java.util.List;

/**530. 二叉搜索树的最小绝对差
 * 注意：这道题不是return(次小值 - 最小值)
 * 而是：对升序数组求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值
 * @author zx
 * @create 2022-04-15 18:03
 */
public class Num530 {
    /**
     * @return 中序遍历
     */
    public int getMinimumDifference(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root,list);
        int res = Integer.MAX_VALUE;
        for(int i = 1;i < list.size();i++){
            res = Math.min(res,(list.get(i) - list.get(i - 1)));
        }
        return res;
    }
    private void inOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }


    /**
     * 中序遍历(官方)
     */
    int pre;
    int res;
    public int getMinimumDifference2(TreeNode root) {
        res = Integer.MAX_VALUE;
        pre = -1;
        inOrder(root);
        return res;
    }
    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            res = Math.min(res, root.val - pre);
            pre = root.val;
        }
        inOrder(root.right);
    }
}
